package com.company.剑指offer每日刷题.普通版;

import java.util.HashMap;
import java.util.Map;

/**
 * 剑指 Offer 50. 第一个只出现一次的字符
 * 在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。
 *
 * 示例 1:
 * 输入：s = "abaccdeff"
 * 输出：'b'
 * 示例 2:
 * 输入：s = ""
 * 输出：' '
 * 限制：
 * 0 <= s 的长度 <= 50000
 * */
public class FirstUniqChar {

    /**
     * 方法1：哈希表，存储
     * */
    public char firstUniqChar(String s) {
        if(s.length() == 0){
            return ' ';
        }
        int res = Integer.MAX_VALUE;
        char[] ch = s.toCharArray();
        Map<Character,Integer> map = new HashMap<>();
        for(int i=0;i<ch.length;i++){
            if(map.containsKey(ch[i])){
                map.put(ch[i],-1);
            }else{
                map.put(ch[i],i);
            }
        }
        for(Integer value:map.values()){
            if(value != -1){
                res = Math.min(value, res);
            }
        }
        return res == Integer.MAX_VALUE? ' ': ch[res];
    }

    /**
     * 方法2：哈希表（优化数据结构和速度）
     *      1.代码判断map的values的地方，我们可以不用遍历所有的元素，只要从左到右去判断每个元素是否重复，然后直接返回这个元素就行了。
     *      2.优化空间占用： 既然1中已经不需要通过map来存储每个元素第一次出现的下标，可将Integer换成boolean，降低空间开支
     * */
    public char firstUniqChar1(String s) {
        if(s.length() == 0){
            return ' ';
        }
        char[] ch = s.toCharArray();
        Map<Character,Boolean> map = new HashMap<>();
        for(int i=0;i<ch.length;i++){
            map.put(ch[i],!map.containsKey(ch[i]));
        }
        for(int i=0;i<ch.length;i++){
            if(map.get(ch[i])) return ch[i];
        }
        return ' ';
    }
}
